package cn.String;

/* ━━━━━━如来保佑━━━━━━
 * 　　   へ　　　　　／|
 * 　　　/＼7　　　∠＿/
 * 　　/　│　　／　／
 * 　　│　Z＿,＜　／　　/`ヽ
 * 　　│　　　　　ヽ　　/　　〉
 * 　　Y　　　　　`　/　　/
 * 　　ｲ●　､　●　　⊂⊃〈　　/
 * 　　()　へ　　　　|　＼〈
 * 　　　>ｰ､_　ィ　│／／
 * 　　/へ　　/　ﾉ＜|＼＼
 * 　　ヽ_ﾉ　　(_／　│／／
 * 
 * ━━━━━━永无BUG━━━━━━
 * @user tianxinxing
 * @date 2019/1/3
 */
//linkcode中的13题
public class KMP {
        public static int getIndex(String str1,String str2){

            return process(str1,str2);
        }

        public static int process(String str1,String str2){
            char[] chars = str1.toCharArray();
            char[] chars1 = str2.toCharArray();
            int[] indexs = getIndexArray(chars1);
            int m1 = 0;
            int m2 = 0;
            //m1不能超过
            while (m1 < str1.length() && m2<str2.length()){
                if (chars[m1] == chars1[m2]) {
                    m1++;
                    m2++;
                } else if(indexs[m2] == -1) {
                    m1++;
                } else {
                    m2 = indexs[m2];
                }
            }

            return m2 == chars1.length ? m1 - m2 : -1;
        }

        public static int[] getIndexArray(char[] chars){
            int[] indexs = new int[chars.length];
            indexs[0] = -1;
            indexs[1] = 0;
            int left = 0;
            int right = 1;
            for (int i = 2; i < chars.length; i++) {
                if(chars[left] == chars[right]){
                    indexs[i] = ++left;
                    right++;
                } else if (left > 0){
                    left  = indexs[i];
                } else {
                    indexs[i] = 0;
                }
            }
            return indexs;
        }

    public static void main(String[] args) {
        String str = "abcabcababaccc";
        String match = "ababa";
        System.out.println(getIndex(str, match));
        System.out.println("".length());
    }
}
